package gold.digger;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC895 {
    public long startExecuteTime = System.currentTimeMillis();


    class FreqStack {

        private Map<Integer, Integer> numCountMap = new HashMap<>();
        private TreeMap<Integer, List<Integer>> cntNumMap = new TreeMap<>();

        public FreqStack() {

        }

        public void push(int val) {
            int cnt = numCountMap.getOrDefault(val, 0) + 1;
            numCountMap.put(val, cnt);//统计值+1
            List<Integer> numList = cntNumMap.get(cnt);
            if (null == numList) numList = new LinkedList<>();
            numList.add(val);
            cntNumMap.put(cnt, numList);
        }

        public int pop() {
            int mostFreCnt = cntNumMap.lastKey();
            int val = cntNumMap.get(mostFreCnt).get(cntNumMap.get(mostFreCnt).size() - 1);
            cntNumMap.get(mostFreCnt).remove(cntNumMap.get(mostFreCnt).size() - 1);
            if (cntNumMap.get(mostFreCnt).size() <= 0) cntNumMap.remove(mostFreCnt);
            numCountMap.put(val, numCountMap.get(val) - 1);
            return val;
        }
    }

    public void run() {
        FreqStack freqStack = new FreqStack();
//        [5,7,5,7,4,5]
        freqStack.push(5);
        freqStack.push(7);
        freqStack.push(5);
        freqStack.push(7);
        freqStack.push(4);
        freqStack.push(5);

        System.out.println(freqStack.pop());
        System.out.println(freqStack.pop());
        System.out.println(freqStack.pop());
        System.out.println(freqStack.pop());
    }

    public static void main(String[] args) throws Exception {
        LC895 an = new LC895();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
